package pri.zjy.statck;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 用队列实现栈  法三：入栈时，就通过队列保持栈的特性（FILO），出栈直接出
 * <p>
 * 复杂度分析：
 * <p>
 * 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)，其中 n 是栈内的元素个数。
 * <p>
 * 入栈操作需要将 queue1中的 n 个元素出队，并入队 n+1 个元素到 queue2，共有 2n+1 次操作，每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。
 * 出栈操作对应将 queue1的前端元素出队，时间复杂度是 O(1)。
 * 获得栈顶元素操作对应获得 queue1的前端元素，时间复杂度是 O(1)。
 * 判断栈是否为空操作只需要判断 queue1是否为空，时间复杂度是 O(1)。
 * <p>
 * 空间复杂度：O(n)，其中 n 是栈内的元素个数。需要使用两个队列存储栈内的元素。
 * <p>
 * @date 2025/3/6 10:19
 */
public class MyStack_225_3 {

    public static void main(String[] args) {
        MyStack_225_3 myStack225 = new MyStack_225_3();
        myStack225.push(1);
        myStack225.push(2);
        System.out.println(myStack225.top()); // 返回 2
        System.out.println(myStack225.pop()); // 返回 2
        System.out.println(myStack225.empty()); // 返回 False

    }

    Queue<Integer> stackQueue = new LinkedList<>();

    Queue<Integer> helpQueue = new LinkedList<>();

    public MyStack_225_3() {
    }

    public void push(int x) {
        // 入栈，通过队列in、out实现栈的FILO

        // 1.辅助队列存新元素
        helpQueue.offer(x);
        // 2.stackQueue的元素全部出队，再压入辅助队列，保证辅助队列最先出的元素是刚刚入队的元素
        while (!stackQueue.isEmpty()) {
            helpQueue.offer(stackQueue.poll());
        }
        // 3.交换两个队列，保证用同一个队列进行出栈操作
        stackQueue = helpQueue;
        helpQueue = new LinkedList<>();
    }

    public int pop() {
        // 出栈，直接出
        return stackQueue.poll();
    }

    public int top() {
        return stackQueue.peek();
    }

    public boolean empty() {
        return stackQueue.isEmpty();
    }

}
